package leetcode.code0935;

import leetcode.IDebug;

public class Solution implements IDebug {

	int mod = (int) 1e9 + 7;

	static int[][] jumps;

	static {
		jumps = new int[10][];
		jumps[0] = new int[] { 4, 6 };
		jumps[1] = new int[] { 6, 8 };
		jumps[2] = new int[] { 7, 9 };
		jumps[3] = new int[] { 4, 8 };
		jumps[4] = new int[] { 0, 3, 9 };
		jumps[5] = new int[] {};
		jumps[6] = new int[] { 0, 1, 7 };
		jumps[7] = new int[] { 2, 6 };
		jumps[8] = new int[] { 1, 3 };
		jumps[9] = new int[] { 2, 4 };
	}

	public int knightDialer(int n) {
		long ans = 0;
		Integer[][] dp = new Integer[10][n + 1];
		for (int i = 0; i < 10; i++) {
			ans += this.find(i, n, dp);
			ans %= mod;
		}
		return (int) ans;
	}

	private int find(int pos, int n, Integer[][] dp) {
		if (pos == 5) {
			return n == 1 ? 1 : 0;
		}
		if (n == 1) {
			return 1;
		}
		if (dp[pos][n] != null) {
			return dp[pos][n];
		}
		int[] jump2 = jumps[pos];
		long ans = 0;
		for (int i = 0; i < jump2.length; i++) {
			ans += this.find(jump2[i], n - 1, dp);
			ans %= mod;
		}
		dp[pos][n] = (int) ans;
		return (int) ans;
	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
//		Solution so = new Solution();
//		int ans = so.knightDialer(3131);
//		System.out.println(ans);

		for (int i = 0; i < 10; i++) {
//			System.out.println(Integer.toBinaryString(i));
			System.out.println(Integer.toBinaryString(~i));
			System.out.println(Integer.toBinaryString(~i & 1));
			System.out.println(i + " " + (~i & 1));
		}

	}

}
